//https://leetcode.cn/problems/find-the-integer-added-to-array-ii/submissions/553833269/?envType=daily-question&envId=2024-08-09

class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end());
        // 排序后找到一个长度为n-2的区间使其差均相等
        int n = nums2.size(), m = nums1.size(), res = INT_MAX;
        for(int i = 0; i < 3; ++i) { // 此处将i从大向小遍历可以不用加res，第一次遇到满足情况的即为答案
            int idx1 = i, idx2 = 0;
            while(idx1 < m && idx2 < n) {
                // 若相等则两个指针同时后移，否则nums1[idx1]应该被移除, 只将idx1后移
                if(nums2[idx2] - nums1[idx1] == nums2[0] - nums1[i]) ++idx2; 
                ++idx1;
            }
            // 若最终nums1中移除的元素个数超过2个则无法完全遍历nums2
            if(idx2 == n) res = min(res, nums2[0] - nums1[i]);
        }
        return res;
    }
};